package lc;

import java.util.Arrays;

public class Ex503 {
    class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int n = nums.length;
            int[] arr = new int[n * 2];
            System.arraycopy(nums, 0, arr, 0, n);
            System.arraycopy(nums, 0, arr, n, n);
            int[] res = new int[n];
            Arrays.fill(res, Integer.MIN_VALUE);
            n *= 2;
            int[] stack = new int[n * 2];
            int idx = -1;
            for (int i = 0; i < n; i++) {
                while (idx >= 0 && arr[stack[idx]] < arr[i]) {
                    int t = stack[idx--]; //小的下标
                    res[t] = arr[i];
                }
                stack[++idx] = i;
            }
            for (int i = 0; i < res.length; i++) {
                if (res[i] < nums[i]) {
                    res[i] = -1;
                }
            }
            return res;
        }
    }
}
